#include<vector>
using namespace std;


class Solution {
public:
    int cnt;
    int reversePairs(vector<int>& nums) {
        cnt = 0;
        mergeSort(nums, 0, nums.size()-1);
        return cnt;

    }
    
    void mergeSort(vector<int>& nums, int left, int right){
        if(left>=right){return;}
        int mid = left+(right-left)/2;
        mergeSort(nums, left, mid);
        mergeSort(nums,mid+1, right);
        merge(nums, left, mid, right);
    }

    void merge(vector<int> &nums, int left, int mid, int right){
        int tmp[right-left+1];
        int i = left;
        int j = mid+1;
        int pos = 0;
        while (i<=mid && j<=right)
        {
            if(nums[i]<=nums[j])tmp[pos++] = nums[i++];
            else{
                cnt += mid-i+1;
                tmp[pos++] = nums[j++];
            }
        }
        while (i<=mid)tmp[pos++] = nums[i++];
        while(j<=right)tmp[pos++] = nums[j++];

        for (int k = 0; k < right-left+1; k++)
        {
            nums[left+k] = tmp[k];
        }
    }
};